A hash function is best understood as a map that sends binary strings of arbitrary length to binary strings of length τ (or hash length).H: {0,1}*→{0,1}τ
This τ value is fixed in advance. Commonly used hash functions have a τ value that varies from 32 to 512 (A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997).
A Message Authentication Code (or MAC) is a hash function that incorporates a key, namely:H: {0,1}*×K→{0,1}τwhere K is a key space. When a user sends data, the hash value, or MAC value of the data is also calculated and appended to the message. The recipient can then verify the integrity of the data by recomputing the hash value or MAC value and comparing it with the one that was appended to the message, thereby enabling the recipient, for example, to authenticate the message.
One of the challenges in providing hash-based data integrity solutions is that the hash value needs to be efficiently computable, and collisions should be improbable. Specifically, given a binary string M, it should be computationally infeasible to find another string M′, satisfying the following equation:H(M)=H(M′)
Hash and MAC algorithms are extremely important and at the same time the most vulnerable systems of network security (A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997). If a hash or MAC value can be determined by an external agency, a “collision” has occurred. If hash or MAC values are subject to collisions, the recipient of data can never be certain that the data in question has not been tampered with or corrupted. Its collision resistance measures the value of a hash (MAC) algorithm. Since the algorithm produces a string of fixed length from a message of any length, it is clear that there will be collisions. However, a good hash algorithm is one for which it is computationally infeasible to create a collision.
In a recent dramatic development, all the main hash algorithms MD-5, RIPEMD, and the MAC algorithm SHA-1 were compromised. Collisions were created for MD-5 and RIPEMD, and a group of Chinese mathematicians managed to reduce the number of operations needed to realise the brute-force attack on SHA-1 to a danger level. It should be noted that SHA-1 is the hash algorithm currently recommended by the US government. Keeping in mind that a lot of different security applications (Kerberos, MIME, IpSec, Digital Signatures and so forth) are using hash algorithms (mainly SHA-1), there is an urgent need to construct new hash algorithms.
All the main hash functions and secure functions, including those mentioned above, are referred to as iterated hash functions. They are based on an idea proposed by Damgard-Merkle (R. C. Merkle, Secrecy, Authentication, and Public Key Systems, UMI Research Press, Ann Arbor, Mich., 1979). According to this idea, the hash function takes an input string of bits, and partitions it into fixed-sized blocks of a certain size q. Then a compression function takes q bits of i-th partition and m bits from the previous calculation and calculates m bits of i+1 iteration. The output value of the last iteration (of size m) is the hash value.
Since it now appears to be easier to create a collision in existing main hash functions and secure functions, the development of new hashing algorithms that would not be based on the Damgard-Merkle approach, is extremely desirable.
Various authors have considered hash algorithms when a message to be hashed is presented as a class of various algebraic objects—elements of fields, groups, etc. Hashing based on polynomial representation is known. One of the most famous approaches is to present data as a collection of polynomials over the field of a certain characteristic. Carter and Wegman (Universal classes of hash functions. J. of Computer and System Sciences 18, 1979, 143-154) proposed the method of presenting a message as coefficients of a polynomial, and a certain point of evaluation of the polynomial is used as a key.
Krovetz and Rogaway (Fast universal hashing with small keys and no preprocessing: the PolyR construction, in: Information Security and Cryptology ICICS 2000, pp. 73-89, ed. D. H. Won, Lecture Notes in Computer Science, 2015, Springer-Verlag, 2000) considered a message as a collection of elements (m0, m1, . . . , mn) of a certain field F. A hash value of the message is a point y∈F, which is computed by calculation in the field F of the value m0kn+m1kn−1+ . . . +mnk0 for some key k∈F.
However, these approaches do not represent the data in terms of polynomials, nor do they compute the hash value using the factorization of these polynomials.
There is a need therefore for methods, computer programs and computer systems that while utilizing hash or MAC algorithms (in particular algorithms of the SHA family) are operable to provide an improved level of security over existing methods, computer programs and computer systems that implement SHA type hash and MAC algorithms. There is a further need for the methods, computer programs and computer systems that meet the aforesaid criteria and are further easy to implement with existing technologies, and are computationally feasible.